Матч 334, Террористы (Terrorists)

Дивизион 1, Уровень 3

Между каждой парой городов страны имеется прямая двусторонняя дорога. Террористы хотят взорвать такое количество дорог, чтобы образовалось хотя бы два города, проезд между которыми был невозможен.

Элемент roads[i][j] содержит стоимость подрыва дороги, ведущей из i - го города в j - ый. Найти наименьшую стоимость, за которую террористам удастся совершить задуманное.

Класс: Terrorists

Метод: int requiredCost(vector<string> roads)

Ограничения: roads содержит от 2 до 50 элементов, roads[i] содержат одинаковое количество символов, которыми являются цифры от 0 до 9, roads[i][i] = 0, roads[i][j] = roads[j][i].

Вход. Массив строк roads, описывающий стоимость подрыва дорог.

Выход. Наименьшая стоимость, за которую террористам удастся сделать сеть городов несвязной.

Пример входа

roads

{"0911",

"9011",

"1109",

"1190"}

{"030900",

"304120",

"040174",

"911021",

"027207",

"004170"}

{"0399",

"3033",

"9309",

"9390"}

Пример выхода

4

8

9

РЕШЕНИЕ

максимальный поток

Рассмотрим граф, в котором города являются вершинами, а двусторонние дороги – неориентированными ребрами. По условию задачи в графе необходимо удалить такое множество ребер, суммарная стоимость которых наименьшая. Это классическая задача о минимальном разрезе. В то же время известно, что минимальный разрез графа равен максимальному потоку. Для любого разреза нулевая вершина будет отделена от какой-нибудь другой. Поэтому находим максимальный поток между нулевой и i - ой (0 < i < n = |V|) вершиной и среди всех значений найденных потоков находим наименьшее.

Функция mincut(s, t) находит величину максимального потока между вершинами s и t. Функция aug(x, t, CurFlow) находит пропускную способность дополняющего пути от вершины x до t, если известно, что пропускная способность дополняющего пути от начальной вершины до x равна CurFlow.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

using namespace std;

int cap[50][50], res[50][50], used[50], n;

struct Terrorists

{

public:

int aug(int x,int t,int CurFlow)

{

if (x == t) return CurFlow;

if (used[x]++) return 0;

for (int Flow, y = 0; y < n; y++)

{

if (res[x][y] > 0 && (Flow = aug(y,t,min(CurFlow,res[x][y]))))

{

res[x][y] -= Flow; res[y][x] += Flow;

return Flow;

}

}

return 0;

}

int mincut(int s, int t)

{

memcpy(res, cap, sizeof(cap));

int x, flow = 0;

do

{

memset(used,0,sizeof(used));

} while ((x = aug(s,t,0x7FFFFFFF)) && (flow += x));

return flow;

}

int requiredCost(vector<string> roads)

{

n = roads.size();

for (int i = 0; i < n; i++)

for (int j = 0; j < n; j++)

cap[i][j] = roads[i][j] - '0';

int best = 0x7FFFFFFF;

for (int s = 1; s < n; s++)

best = min(best,mincut(0, s));

return best;

}

};